package practice;

import struct.BinaryTree;
import struct.interfaces.TreeNode;

/**
 * 给定一个二叉树，计算整个树的坡度。
 * <p>
 * 一个树的节点的坡度定义即为，该节点左子树的结点之和和右子树结点之和的差的绝对值。空结点的的坡度是0。
 * <p>
 * 整个树的坡度就是其所有节点的坡度之和。
 * <p>
 * 输入:
 * 1
 * /   \
 * 2     3
 * 输出: 1
 * 解释:
 * 结点的坡度 2 : 0
 * 结点的坡度 3 : 0
 * 结点的坡度 1 : |2-3| = 1
 * 树的坡度 : 0 + 0 + 1 = 1
 */
public class _563_BinaryTreeTilt {

    int value;

    public static void main(String[] args) {
        BinaryTree root = new BinaryTree(1,2,3);
        root.getLeftNode().setLeftNode(new BinaryTree(4));
        root.getRightNode().setLeftNode(new BinaryTree(5));
        System.out.println(new _563_BinaryTreeTilt().findTilt(root));
    }

    /**
     * 后序遍历，先计算子节点的坡度，再计算根节点的坡度，最后累加
     *
     * @param root
     * @return
     */
    public int findTilt(BinaryTree root) {
        if (root == null) {
            return 0;
        }
        postOrder(root);
        return value;
    }

    /**
     * 返回当前二叉树所有节点的和
     * @param root
     * @return
     */
    private int postOrder(BinaryTree root) {
        if (root == null) {
            return 0;
        }
        int left = postOrder(root.getLeftNode());
        int right = postOrder(root.getRightNode());
        value += Math.abs(left - right);
        return left + right + root.getValue();
    }
}